package com.tencent.teg.cspf;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Graph {

    private static Integer MAX_VALUE = Integer.MAX_VALUE / 2;

    private Map<Integer, Node> nodeMap = null;
    private Map<Integer, Link> linkMap = null;

    private Map<Node, List<Link>> srcLinkListMap = null;
    private Map<Node, List<Link>> dstLinkListMap = null;

    public Graph() {
        this.nodeMap = new HashMap<>();
        this.linkMap = new HashMap<>();

        this.srcLinkListMap = new HashMap<>();
        this.dstLinkListMap = new HashMap<>();
    }

    private void processGraphData() {
        for (Integer linkId : linkMap.keySet()) {
            Link link = this.linkMap.get(linkId);
            Node srcNode = link.getSrcNode();
            Node dstNode = link.getDstNode();

            if (this.srcLinkListMap.containsKey(srcNode)) {
                this.srcLinkListMap.get(srcNode).add(link);
            } else {
                List<Link> srcLinkList = new ArrayList<>();
                srcLinkList.add(link);
                this.srcLinkListMap.put(srcNode, srcLinkList);
            }

            if (this.dstLinkListMap.containsKey(dstNode)) {
                this.dstLinkListMap.get(dstNode).add(link);
            } else {
                List<Link> dstLinkList = new ArrayList<>();
                dstLinkList.add(link);
                this.dstLinkListMap.put(dstNode, dstLinkList);
            }
        }
    }

    public void readGraphFromFile() {

        String lowNodeSrcFile = "C:/Resources/test/dcitopo_low/data/node.dat";
        String lowLinkSrcFile = "C:/Resources/test/dcitopo_low/data/link.dat";

        int index = 0;
        String lineContent = null;
        File nodeFile = new File(lowNodeSrcFile);
        Map<String, Node> nodeNameMap = new HashMap<>();
        try {
            BufferedReader nodeReader = new BufferedReader(new InputStreamReader(new FileInputStream(nodeFile), "UTF-8"));
            nodeReader.readLine();

            index = 0;
            while ((lineContent = nodeReader.readLine()) != null) {
                /** Format:
                 * number node_name node_city
                 * 0      A	    Beijing
                 */
                String[] strings = lineContent.split("\\s+");

                Node node = new Node();
                node.setId(index);
                node.setName(strings[1]);

                this.nodeMap.put(index, node);
                nodeNameMap.put(strings[1], node);
                index++;
            }

            nodeReader.close();
        } catch (Exception e) {
            e.printStackTrace();
        }

        File linkFile = new File(lowLinkSrcFile);
        try {
            BufferedReader linkReader = new BufferedReader(new InputStreamReader(new FileInputStream(linkFile), "UTF-8"));
            linkReader.readLine();

            index = 0;
            while ((lineContent = linkReader.readLine()) != null) {
                // Format:
                // number link_name link_type    bandwidth(MB) metric delay
                // 0	  SZ1-SZ2   1            410000		   100	  20
                String[] strings = lineContent.split("\\s+");

                Link link = new Link();
                link.setId(index);
                link.setName(strings[1]);
                link.setBandwidth(Integer.parseInt(strings[3]));
                link.setMetric(Integer.parseInt(strings[4]));
                link.setDelay(Integer.parseInt(strings[5]));

                String[] srcDstStrs = strings[1].split("-");
                String srcNodeName = srcDstStrs[0];
                Node srcNode = nodeNameMap.get(srcNodeName);
                String dstNodeName = srcDstStrs[1];
                Node dstNode = nodeNameMap.get(dstNodeName);

                link.setSrcNode(srcNode);
                link.setDstNode(dstNode);

                this.linkMap.put(index, link);
                index++;
            }

            linkReader.close();
        } catch (Exception e) {
            e.printStackTrace();
        }

        System.out.println("Topo Node Count = " + this.nodeMap.size());
        System.out.println("Topo Link Count = " + this.linkMap.size());
        this.processGraphData();
    }

    public void cspfHandler(SpfRequest request) {
        SpfResponse response = new SpfResponse();

        Set<Link> downLinkSet = new HashSet<>();

        for (Map.Entry<Integer, Link> entry : this.linkMap.entrySet()) {
            Link link = entry.getValue();
            if (link.getBandwidth() < request.getBwRequest())
                downLinkSet.add(link);
        }

        Node srcNode = this.nodeMap.get(request.getSrcNodeId());
        Node dstNode = this.nodeMap.get(request.getDstNodeId());

        Set<Node> unvisitNodeSet = new HashSet<>();
        Map<Node, Integer> nodeDistanceMap = new HashMap<>();
        Map<Node, Link> nodePrevLinkMap = new HashMap<>();

        Map<Node, Integer> nodeDelayMap = new HashMap<>();
        Map<Node, Integer> nodeHopMap = new HashMap<>();

        for (Map.Entry<Integer, Node> entry : this.nodeMap.entrySet()) {
            Node node = entry.getValue();

            unvisitNodeSet.add(node);
            nodeDistanceMap.put(node, MAX_VALUE);
        }

        unvisitNodeSet.remove(srcNode);
        nodeDistanceMap.put(srcNode, 0);
        nodeHopMap.put(srcNode, 1);
        nodeDelayMap.put(srcNode, 0);

        for (Link link : this.srcLinkListMap.get(srcNode)) {
            if (downLinkSet.contains(link))
                continue;

            Node nextHop = link.getDstNode();

            Integer newHop = nodeHopMap.get(srcNode) + 1;
            Integer newDelay = nodeDelayMap.get(srcNode) + 1;

            if (newHop > request.getHopRequest() || newDelay > request.getDelayRequest())
                continue;

            Integer oldCost = nodeDistanceMap.get(nextHop);
            Integer newCost = link.getMetric();

            if (oldCost != null && oldCost < newCost)
                continue;

            nodeDistanceMap.put(nextHop, newCost);
            nodePrevLinkMap.put(nextHop, link);
        }

        while (!unvisitNodeSet.isEmpty()) {
            Node minNode = null;
            Integer minTmp = MAX_VALUE;

            for (Node node : unvisitNodeSet) {
                if (nodeDistanceMap.get(node) < minTmp) {
                    minNode = node;
                    minTmp = nodeDistanceMap.get(node);
                }
            }

            System.out.println("Min Node Name = " + minNode.getName());

            if (minNode == null) {
                System.out.println("No path.");
                return;
            }

            if (minNode == dstNode) {
                System.out.println("Have path.");
                break;
            }

            Link prevLink = nodePrevLinkMap.get(minNode);
            Integer hop = nodeHopMap.get(prevLink.getSrcNode()) + 1;
            Integer delay = nodeDelayMap.get(prevLink.getSrcNode()) + prevLink.getDelay();
            nodeHopMap.put(minNode, hop);
            nodeDelayMap.put(minNode, delay);
            unvisitNodeSet.remove(minNode);

            for (Link link : this.srcLinkListMap.get(minNode)) {
                if (downLinkSet.contains(link))
                    continue;

                Node nextHop = link.getDstNode();

                System.out.println("Node name = " + nextHop.getName());
                Integer newHop = nodeHopMap.get(minNode) + 1;
                Integer newDelay = nodeDelayMap.get(minNode) + link.getDelay();
                if (newHop > request.getHopRequest() || newDelay > request.getDelayRequest()) {
                    System.out.println("Hop Name = " + nextHop.getName());
                    continue;
                }

                Integer oldCost = nodeDistanceMap.get(nextHop);
                Integer newCost = minTmp + link.getMetric();

                if (oldCost < newCost)
                    continue;

                nodeDistanceMap.put(nextHop, newCost);
                nodePrevLinkMap.put(nextHop, link);

            }
        }

        Node tmpNode = dstNode;
        while (!tmpNode.equals(srcNode)) {
            response.addPathNode(tmpNode);

            Link link = nodePrevLinkMap.get(tmpNode);
            response.addPathLink(link);

            tmpNode = link.getSrcNode();
        }

        response.addPathNode(srcNode);

        response.printPath();
    }
}


class SpfRequest {
    private int srcNodeId = 0;
    private int dstNodeId = 0;
    private int bwRequest = 0;
    private int delayRequest = 0;
    private int hopRequest = 0;

    public SpfRequest() {

    }

    public int getSrcNodeId() {
        return srcNodeId;
    }

    public void setSrcNodeId(int srcNodeId) {
        this.srcNodeId = srcNodeId;
    }

    public int getDstNodeId() {
        return dstNodeId;
    }

    public void setDstNodeId(int dstNodeId) {
        this.dstNodeId = dstNodeId;
    }

    public int getBwRequest() {
        return bwRequest;
    }

    public void setBwRequest(int bwRequest) {
        this.bwRequest = bwRequest;
    }

    public int getDelayRequest() {
        return delayRequest;
    }

    public void setDelayRequest(int delayRequest) {
        this.delayRequest = delayRequest;
    }

    public int getHopRequest() {
        return hopRequest;
    }

    public void setHopRequest(int hopRequest) {
        this.hopRequest = hopRequest;
    }
}

class SpfResponse {
    private List<Link> pathLinkList = null;
    private List<Node> pathNodeList = null;

    public SpfResponse() {
        this.pathLinkList = new ArrayList<>();
        this.pathNodeList = new ArrayList<>();
    }

    public void addPathLink(Link link) {
        this.pathLinkList.add(link);
    }

    public void addPathNode(Node node) {
        this.pathNodeList.add(node);
    }

    public void printPath() {
        System.out.println("Path Node List: ");
        for (Node node : this.pathNodeList)
            System.out.print(" " + node.getName() + " ");

        System.out.println("\nPath Link List: ");
        for (Link link : this.pathLinkList)
            System.out.print(" " + link.getName() + " ");

        System.out.println();
    }
}